package day_2022_9_to_12.Day;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/10/16 15:55
 **/
public class Day44_1_Num886_PossibleBipartition {
    class Solution {
        public boolean possibleBipartition(int n, int[][] dislikes) {
            int[] arr = new int[n+1];
            for(int i = 0; i < dislikes.length; ++i){
                int[] ret = dislikes[i];
                int l = ret[0], r = ret[1];
                if(arr[l] == 0 && arr[r] == 0){
                    arr[l] = -1;
                    arr[r] = 1;
                }else if(arr[l] != 0 && arr[r] == 0){
                    arr[r] = -arr[l];
                }else if(arr[l] == 0 && arr[r] != 0){
                    arr[l] = -arr[r];
                }else if(arr[l] != 0 && arr[r] != 0){
                    if(arr[l] == arr[r]) return false;
                }
            }
            return true;
        }
    }
    class Solution2 {
        private List<Integer>[] g;
        private int[] color;

        public boolean possibleBipartition(int n, int[][] dislikes) {
            g = new List[n];
            color = new int[n];
            for (int i = 0; i < n; ++i) {
                g[i] = new ArrayList<>();
            }
            for (int[] e : dislikes) {
                int a = e[0] - 1, b = e[1] - 1;
                g[a].add(b);
                g[b].add(a);
            }
            for (int i = 0; i < n; ++i) {
                if (color[i] == 0) {
                    if (!dfs(i, 1)) {
                        return false;
                    }
                }
            }
            return true;
        }

        private boolean dfs(int i, int c) {
            color[i] = c;
            for (int j : g[i]) {
                if (color[j] == c) {
                    return false;
                }
                if (color[j] == 0 && !dfs(j, 3 - c)) {
                    return false;
                }
            }
            return true;
        }
    }


}